package com.LeeCode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 你可以安排的最多任务数目
 */

public class Code2071 {
    public static void main(String[] args) {
        int[] tasks = {3, 2, 1};
        int[] workers = {0, 3, 3};
        int pills = 1, strength = 1;
        System.out.println(new Code2071().maxTaskAssign(tasks, workers, pills, strength));
    }

    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        // 对任务和工人进行排序--从小到大
        Arrays.sort(tasks);
        Arrays.sort(workers);

        // 闭区间二分，left 和 right 都是可能的结果
        int left = 0;
        int right = Math.min(tasks.length, workers.length);  // 最多能完成的任务
        int ans = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(tasks, workers, pills, strength, mid)) {  // 可行，尝试更大的值
                ans = mid;
                left = mid + 1;
            } else {  // 否则，更换更小的值
                right = mid - 1;
            }
        }

        return ans;
    }

    private boolean check(int[] tasks, int[] workers, int pills, int strength, int k) {
        // 贪心策略：用最强的 k 名工人完成最简单的 k 个任务，每个工人必须完成一个任务
        // 使用双端队列维护当前可完成的任务
        Deque<Integer> validTasks = new ArrayDeque<>();
        int i = 0;  // 当前第几个任务
        int pi = pills;  // 可用药丸数

        // 枚举最强的 k 名工人（排序后的最后 k 个工人）
        for (int j = workers.length - k; j < workers.length; j++) {
            int worker = workers[j];

            // 在吃药的情况下，将当前工人能完成的任务加入队列
            while (i < k && tasks[i] <= worker + strength) {
                validTasks.addLast(tasks[i]);
                i++;
            }
            // 即使吃药，也没有任务可以完成
            if (validTasks.isEmpty()) {
                return false;
            }
            // 如果工人不吃药就能完成最简单的任务，优先完成
            if (worker >= validTasks.peekFirst()) {
                validTasks.pollFirst();
                continue;
            }
            // 必须完成一项，所以必须吃药
            if (pi <= 0) {  // 没有药了，无法完成
                return false;
            }
            // 吃药后完成这个工人能完成的最难的任务（队列末尾）
            pi--;
            validTasks.pollLast();
        }
        return true;
    }
}
